class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int row = mat.length; // 行
        int col = mat[0].length; // 列
        // 填充前缀和数组
        int[][] v_nums = new int[row+1][col+1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                v_nums[i][j] = v_nums[i-1][j]+v_nums[i][j-1]-v_nums[i-1][j-1]+mat[i-1][j-1];
            }
        }
        // 填充ans数组
        int[][] ans = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 这里可以在坐标上面+1，这样公式就不用改了
                int x1 = Math.max(0, i-k) + 1;
                int y1 = Math.max(0, j-k) + 1;
                int x2 = Math.min(row-1, i+k) + 1;
                int y2 = Math.min(col-1, j+k) + 1;
                ans[i][j] = v_nums[x2][y2]-v_nums[x1-1][y2]-v_nums[x2][y1-1]+v_nums[x1-1][y1-1];
            }
        }
        return ans;
    }
}